package NM;

public class MyLinkedList implements IList {
    static class ListNote{
        public int val;
        public ListNote prev;
        public ListNote next;

        public ListNote(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "ListNote{" +
                    "val=" + val +
                    '}';
        }
    }
    public ListNote head;//定义头结点；
    public ListNote last;//定义尾结点

//打印一个带头双向链表；；
    @Override
    public void disPlay() {
        ListNote cur=head;
        while (cur!=null){
            System.out.println(cur+" ");
            cur=cur.next;
        }
    }
//计算链表长度；
    @Override
    public int size() {
        int len=0;
        ListNote cur=head;
        while (cur!=null){
            len++;
            cur=cur.next;
        }
        return len;
    }
    //判断链表中是否包含key;

    @Override
    public boolean contains(int key) {
        ListNote cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //双向链表头插法；

    @Override
    public void addFirst(int date) {
        ListNote node = new ListNote(11);
        if (head == null) {
            head = last = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }
    //双向链表尾插法；

    @Override
    public void addLast(int date) {
        ListNote node = new ListNote(11);
        if (head == null) {
            head = last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = last.next;
        }
    }
    //向指定位置插入对应的数据；


    @Override
    public void addIndex(int intdex, int date) {
        ListNote node=new ListNote(12);
       int len=size();
       if(intdex < 0||intdex>len){
           return;
       }
       if(intdex==0){
           addFirst(date);
           return;
       }
       if(intdex==len){
           addLast(date);
           return;
       }
       //中间插入；
        ListNote cur=findIndex(date);
       node.next=cur;
       cur.prev.next=node;
       node.prev=cur.prev;
       cur.prev=node;
    }
    private ListNote findIndex(int intdex){
        ListNote cur=head;
        while(intdex!=0){
            cur=cur.next;
            intdex--;
        }
        return cur;
    }
//删除某个节点；
    @Override
    public void remove(int key) {
        ListNote cur=head;
        while(cur!=null){
            if(cur.val==key){
                //开始删除；
                if(cur==head) {
                    head = head.next;
                    if (head != null) {
                        head.prev = null;
                    }
                }else{
                    cur.prev.next=cur.next;
                    if(cur.next==null){
                        last=last.next;
                    }
                    cur.next.prev=cur.prev;
                }
                return;
            }
            cur=cur.next;
        }

    }

    @Override
    public void clear() {
        ListNote cur=head;
        while(cur!=null){
            ListNote curN=cur.next;
            cur.prev=null;
            cur.next=null;
            cur=curN;
        }
        head=last=null;
    }
    //编写代码，以给定值x为基准将链表分割成两部分，所有小于x的节点排在大于或等于x的节点之前；
    public ListNote partition(int x){
        ListNote bs=null;
        ListNote be=null;
        ListNote as=null;
        ListNote ae=null;
        ListNote cur=head;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=be=cur;
                }else{
                    be.next=cur;
                    be=be.next;
                }
            }else{
                if(as==null){
                    as=ae=null;
                }else{
                    ae.next=cur;
                    ae=ae.next;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
        }
        be.next=as;
        if(as!=null){
            ae.next=null;
        }
        return bs;

    }
    //给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回null;
    public ListNote detectCycle(){
        ListNote fast=head;
        ListNote slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;
        }
        slow=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
//链表的回文结构；
    //方法1.找链表的中间节点；
    //....2.反向链表的中间后后半部分；
    //....3.对其前后进行一一遍历；
    public boolean chkPalindrome(){
        if(head==null){
            return true;
        }
        ListNote fast=head;
        ListNote slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNote cur=slow.next;
        while(cur!=null){
            ListNote curN=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curN;
        }
        while(head!=slow){
            if(head.val!=slow.val){
                return false;
            }
            if(head.next==slow){
                return true;
            }
            head=head.next;
            slow=slow.next;

        }
        return true;

    }
}
